package tree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class buildTreeDfs {
    public TreeNode buildTree(List<Integer> list){
        if (list.isEmpty()){
            return null;
        }
        Deque<TreeNode> que = new LinkedList<>();
        TreeNode root = new TreeNode(list.get(0));
        que.offerLast(root);
        int i = 1;
        while (!que.isEmpty() && i < list.size()){
            TreeNode current = que.pollFirst();
            if (i < list.size() && list.get(i) != null) {
                current.left = new TreeNode(list.get(i));
                que.offerLast(current.left);
            }
            i++;
            // Right child
            if (i < list.size() && list.get(i) != null) {
                current.right = new TreeNode(list.get(i));
                que.offerLast(current.right);
            }
            i++;
        }
        return root;
    }
}
